The present invention relates in general to computer-based rendering systems and in particular to rendering techniques for clipping geometry by addition of vertices to existing primitives.
Three-dimensional (3D) rendering systems typically operate as pipelines. The pipeline receives geometry data in the form of primitives (usually lines and/or triangles) that represent various objects making up a scene. The primitives are generally defined by specifying vertices having spatial coordinates and other attributes, such as color components, texture coordinates, and the like. After a first pipeline stage transforms all of the objects to a common world coordinate system, the next pipeline stage transforms the objects to a viewing coordinate system, which is often expressed in 3D homogeneous (projective) coordinates (x, y, z, w), where all vectors (tx, ty, tz, tw) for t≠0 project to a single point (x/w, y/w, z/w) in 3D space. The viewing coordinate system typically has its origin at an eyepoint and a view direction coincident with the z axis; points with coordinate w<0 are “behind” the eyepoint. A screen plane parallel to the xy plane (usually at w=1) is defined, and the geometry is projected onto the screen plane by transforming to inhomogeneous screen coordinates (X, Y, Z). In some cases, the screen coordinates are defined in two dimensions as (X, Y) with the Z coordinate being saved as a vertex attribute. A rasterization algorithm defines a pixel array (raster) over a visible portion of the screen and determines which of the various primitives is visible at each pixel location on the screen so that pixels can be colored accordingly.
Projection of geometry onto the screen generally involves defining a viewable volume, e.g., so that objects located behind the eyepoint are not drawn. The viewable volume is typically identified by defining a view frustum that includes a near plane and a far plane (both parallel to the plane of the screen), as well as edge planes projected from the eyepoint that intersect the screen plane at approximately the edges of the raster. The near plane is generally defined to be somewhat in front of the eyepoint (e.g., at some w for which 0<w<1); the far plane is defined so as to exclude objects that are too remote from the eyepoint to be of interest. The edge planes can be used to exclude primitives (or portions thereof) that extend beyond the edges of the raster.
Often, the geometry includes primitives that extend partly into the view frustum and partly outside it. FIG. 1A illustrates a triangle 102 having vertices 104, 106, 108 that intersects a near plane 110 of a view frustum, as seen from the side. (An eyepoint 100 is shown for reference.) Shaded portion 112, which is outside the view frustum, should not be drawn by the rasterizer.
Clipping, illustrated in FIG. 1B, prevents shaded portion 112 from being drawn by eliminating it from the geometry provided to the rasterizer. In a typical implementation of clipping, two new vertices 114 and 115 are created where the edges of triangle 102 intersect near plane 110. Vertex creation generally involves computing new vertex coordinates, e.g., by finding the intersection of the edge and the clipping plane, and computing new values for any attributes, e.g., color component values, a Z value in 2D screen coordinates, e.g., by interpolation. Triangle 102 is then divided into two new triangles 116, 118, both of which are entirely contained within the visible volume defined by near plane 110. Triangles 116, 118 are each provided to the rasterizer. (Creation of two triangles is generally necessary as typical rasterizers and shaders are not configured to handle primitives with more than three vertices.) Thus, clipping removes the invisible portions of primitives to support correct rendering, but at the cost of creating additional geometry, which increases the processing power required at subsequent stages.
To avoid creating new primitives, “clipless” rasterizers have been developed. Clipless rasterizers use the homogeneous coordinates and avoid creating new vertices. One such rasterizer, described by Olano and Greer, defines an “external” triangle projection onto the screen plane for any triangle that has a vertex behind the eyepoint (w<0 in projective coordinates) and uses the external triangle to determine pixel coverage. FIGS. 1C-D illustrate this concept. FIG. 1C shows (in side view) a triangle 120 with a vertex 122 that is behind eyepoint 124. To rasterize triangle 120 using the Olano and Greer technique, vertices 126 and 128 (at positive w) are projected toward eyepoint 124 onto a screen plane 130 (at points 126′ and 128′, respectively), and vertex 122 (at negative w) is projected through eyepoint 124 and onto screen 130 at point 122′. The resulting triangle 132 is shown in a screen view in FIG. 1D. Triangle 132 is an external triangle, meaning that its edge equations are defined in such a manner that the rasterizer treats points in shaded region 134 as being inside triangle 132, while points in unshaded region 136 are treated as being outside triangle 132. Shaded region 134 does not have a defined upper boundary; the upper boundary is provided naturally by the edge of the raster. (This accurately reflects what the viewer at eyepoint 124 in FIG. 1C would see.)
A clipless rasterizer can be faster than clipping because no new primitives are created. Implementing clipless rasterizers, however, is complicated in part by the finite numerical precision available in typical graphics processing hardware, and significant errors can result when negative-w vertices (e.g., vertex 122 of FIG. 1C) are projected onto the screen plane.
It would therefore be desirable to provide clipping techniques that can eliminate points behind the eye without creating additional geometry.